package com.asa.suanfa.bean;

public class TreePoint {
	
//	性质1. 节点是红色或黑色。
//	性质2. 根节点是黑色。
//	性质3 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
//	性质4. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点
	
	public Comparable<Comparable> asa;//值
	public TreePoint left;//左节点
	public TreePoint right;//右节点

	public TreePoint parent;//父节点
	
	public boolean isred;//红黑树，这个点不是红色，那就是黑色了
	
	/**
	 * 左旋
	 * @return
	 */
	public boolean zuoxian() {
		//判断是父节点的左节点，或者是右节点
		if (this.parent!=null) {
			boolean pleft = false;
			if (this.parent.left!=null) {
				pleft = this.parent.left.equals(this);
			}
//			boolean pright = this.parent.right.equals(this);
			if (pleft) {
				parent.left = this.right;
				this.right.parent = this.parent;
			}else {
				parent.right = this.right;
				this.right.parent = this.parent;
			}
		}
		
		this.parent = this.right;
		this.right.left = this;
		
		this.right.left.parent = this;
		this.right = this.right.left;
		
		
		return false;
	}
	
	/**
	 * 右旋
	 * @return
	 */
	public boolean youxian() {
		
		
		//判断是父节点的左节点，或者是右节点
		if (this.parent!=null) {
			boolean pleft = false;
			if (this.parent.left!=null) {
				pleft = this.parent.left.equals(this);
			}
//			boolean pright = this.parent.right.equals(this);
			if (pleft) {
				parent.left = this.right;
				this.left.parent = this.parent;
			}else {
				parent.right = this.right;
				this.left.parent = this.parent;
			}
		}
		
		this.parent = this.left;
		this.left.right = this;
		
		this.left.right.parent = this;
		this.left = this.left.right;

		return false;
	}
	
	public void addleft(TreePoint treePoint) {
		
		if (isred) {//当前加入节点的父节点是红色时
			//父节点和叔叔节点改为黑色
			this.parent.left.isred = false;
			this.parent.right.isred = false;
			//将爷爷节点改为红色
			this.parent.parent.isred = true;
			
			if (this.parent.parent.parent.isred) {
				if (this.parent.parent.parent.right.equals(this.parent.parent)) {
					//如果爷爷节点是祖爷爷的右节点，左旋，否则右旋
					this.parent.parent.parent.zuoxian();
				}else {
					this.parent.parent.parent.youxian();
				}
				
				if (this.parent.parent.parent.parent.left.equals(this.parent.parent.parent)) {
					this.parent.parent.parent.isred = false;
					this.parent.parent.parent.parent.isred = true;
					this.parent.parent.parent.parent.youxian();
				}else {
					this.parent.parent.parent.isred = false;
					this.parent.parent.parent.parent.isred = true;
					this.parent.parent.parent.parent.zuoxian();
				}
				
			}
			
			
			

		}
		this.left = treePoint;
		treePoint.parent = this;	
	}
	public void addright(TreePoint treePoint) {
		
		if (isred) {//当前加入节点的父节点是红色时
			this.parent.left.isred = false;
			this.parent.right.isred = false;
			this.parent.parent.isred = true;

		}
		this.right = treePoint;
		treePoint.parent = this;	
	}
	
	
	
	
	public void treeadd(TreePoint treePoint) {
		//默认新加入的节点是红树
		treePoint.isred = true;
		TreePoint pretreePoint = this;//当前比较节点

		while(true) {
			
			int compareTo = pretreePoint.asa.compareTo(treePoint.asa);
			if (compareTo>0) {
				pretreePoint = pretreePoint.left;
			}else {
				pretreePoint = pretreePoint.right;
			}
			if (pretreePoint==null) {
				
			}
			
			
		}
		
		
		
		
	}
	
	
	
}
